home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / graphics / sweep_segments.c < prev    next >
C/C++ Source or Header  |  1994-08-05  |  21KB  |  945 lines
  1. #include <LEDA/prio.h>
  2. #include <LEDA/sortseq.h>
  3. #include <LEDA/segment.h>
  4. #include <LEDA/window.h>
  5.  
  6. #include <math.h>
  7.  
  8.  
  9.  
  10. /*
  11. #include <LEDA/graph.h>
  12.  
  13. */
  14.  
  15.  
  16.  
  17. #define EPS  0.00001
  18. #define EPS2 0.0000000001
  19.  
  20.  
  21. window* Wp;
  22.  
  23. static bool trace = false;
  24. static bool intera = false;
  25. static color seg_color = blue;
  26. static color node_color = red;
  27.  
  28.  
  29. class SWEEP_POINT;
  30. class SWEEP_SEGMENT;
  31. typedef SWEEP_POINT* SWEEP_point;
  32. typedef SWEEP_SEGMENT* SWEEP_segment;
  33.  
  34. enum SWEEP_point_type {Cross=0,Rightend=1,Leftend=2}; 
  35.  
  36.  
  37. class SWEEP_POINT
  38. {
  39.   friend class SWEEP_SEGMENT;
  40.  
  41.   SWEEP_segment seg;
  42.   int     kind;
  43.   double    x,y;
  44.  
  45.   public:
  46.  
  47.   SWEEP_POINT(double a,double b)   { x=a; y=b; seg=0; kind=Cross;}
  48.  
  49.   SWEEP_POINT(point p)         { x=p.xcoord();y=p.ycoord();seg=0;kind=Cross;}
  50.  
  51.   friend double    get_x(SWEEP_point p);
  52.   friend double    get_y(SWEEP_point p);
  53.   friend int       get_kind(SWEEP_point p);
  54.   friend SWEEP_segment get_seg(SWEEP_point p);
  55.  
  56.   friend bool intersection(SWEEP_segment, SWEEP_segment, SWEEP_point&);
  57.  
  58.   LEDA_MEMORY(SWEEP_POINT);
  59.  
  60. };
  61.  
  62.   inline double    get_x(SWEEP_point p)       { return p->x; }
  63.   inline double    get_y(SWEEP_point p)       { return p->y; }
  64.   inline int       get_kind(SWEEP_point p)    { return p->kind; }
  65.   inline SWEEP_segment get_seg(SWEEP_point p) { return p->seg; }   
  66.  
  67.  
  68. int compare(const SWEEP_point& p1, const SWEEP_point& p2)
  69. { if (p1==p2) return 0;
  70.  
  71.   double diffx = get_x(p1) - get_x(p2);
  72.   if (fabs(diffx) > EPS2 ) return (diffx > 0.0) ? 1 : -1;
  73.  
  74.   int  diffk = get_kind(p1)-get_kind(p2);
  75.   if (diffk != 0) return diffk;
  76.  
  77.   double diffy = get_y(p1) - get_y(p2);
  78.   if (fabs(diffy) > EPS2 ) return (diffy > 0.0) ? 1 : -1;
  79.  
  80.   return 0;
  81.  
  82. }
  83.  
  84. void Print(SWEEP_point& p) { cout << string("(%f,%f)",get_x(p), get_y(p)); }
  85.  
  86.  
  87.  
  88.  
  89. class SWEEP_SEGMENT
  90. {
  91.   SWEEP_point startpoint;
  92.   SWEEP_point endpoint;
  93.   double  slope;
  94.   double  yshift;
  95.   //node  left_node;
  96.   int   orient;
  97.   int   color;
  98.   int   name;
  99.  
  100.   public:
  101.  
  102.   SWEEP_SEGMENT(SWEEP_point, SWEEP_point,int,int);     
  103.  ~SWEEP_SEGMENT() { delete startpoint; delete endpoint; }     
  104.  
  105.   friend SWEEP_point get_startpoint(SWEEP_segment seg);
  106.   friend SWEEP_point get_endpoint(SWEEP_segment seg);
  107.   friend double get_slope(SWEEP_segment seg);
  108.   friend double get_yshift(SWEEP_segment seg);
  109.   friend int  get_orient(SWEEP_segment seg);
  110.   friend int  get_color(SWEEP_segment seg);
  111.   friend int  get_name(SWEEP_segment seg);
  112.  
  113. /*
  114.   friend node get_left_node(SWEEP_segment seg)         { return seg->left_node;}
  115.   friend void set_left_node(SWEEP_segment seg, node v) { seg->left_node = v; }
  116. */
  117.  
  118.   friend bool intersection(SWEEP_segment, SWEEP_segment, SWEEP_point&);
  119.  
  120.   LEDA_MEMORY(SWEEP_SEGMENT);
  121.  
  122.  
  123. };
  124.  
  125.  
  126. inline SWEEP_point get_startpoint(SWEEP_segment seg) { return seg->startpoint; }
  127. inline SWEEP_point get_endpoint(SWEEP_segment seg)   { return seg->endpoint; }
  128. inline double get_slope(SWEEP_segment seg)           { return seg->slope; }
  129. inline double get_yshift(SWEEP_segment seg)          { return seg->yshift; }
  130. inline int  get_orient(SWEEP_segment seg)            { return seg->orient; }
  131. inline int  get_color(SWEEP_segment seg)             { return seg->color; }
  132. inline int  get_name(SWEEP_segment seg)              { return seg->name; }
  133.  
  134.  
  135.   SWEEP_SEGMENT::SWEEP_SEGMENT(SWEEP_point p1,SWEEP_point p2,int c, int n)    
  136.   {
  137.     //left_node  = nil;
  138.     color      = c;
  139.     name       = n;
  140.  
  141.     if (compare(p1,p2) < 0)
  142.      { startpoint = p1; 
  143.        endpoint = p2; 
  144.        orient = 0;
  145.       }
  146.     else
  147.      { startpoint = p2; 
  148.        endpoint = p1; 
  149.        orient = 1;
  150.       }
  151.  
  152.     startpoint->kind = Leftend; 
  153.     endpoint->kind = Rightend; 
  154.     startpoint->seg = this; 
  155.     endpoint->seg = this;
  156.  
  157.     if (endpoint->x != startpoint->x)
  158.     {
  159.       slope = (endpoint->y - startpoint->y)/(endpoint->x - startpoint->x);
  160.       yshift = startpoint->y - slope * startpoint->x;
  161.  
  162.       startpoint->x -= EPS;
  163.       startpoint->y -= EPS * slope;
  164.       endpoint->x += EPS;
  165.       endpoint->y += EPS * slope;
  166.     }
  167.     else //vertical segment
  168.     { startpoint->y -= EPS;
  169.       endpoint->y   += EPS;
  170.      }
  171.   }
  172.  
  173. void Print(SWEEP_segment& s) { cout << string("S%d",get_name(s)); }
  174.  
  175. static double x_sweep;
  176. static double y_sweep;
  177.  
  178.  
  179. int compare(const SWEEP_segment& s1,const SWEEP_segment& s2)
  180. {
  181.   double sl1 = get_slope(s1);
  182.   double sl2 = get_slope(s2);
  183.   double ys1 = get_yshift(s1);
  184.   double ys2 = get_yshift(s2);
  185.  
  186.   double y1 = sl1*x_sweep+ys1;
  187.   double y2 = sl2*x_sweep+ys2;
  188.  
  189.   double diff = y1-y2;
  190.  
  191.   if (fabs(diff) > EPS2) return (diff > 0.0) ? 1 : -1;
  192.  
  193.   if (sl1 == sl2) 
  194.         return compare(get_x(get_startpoint(s1)), get_x(get_startpoint(s2)));
  195.  
  196.     if (y1 <= y_sweep+EPS2)
  197.         return compare(sl1,sl2);
  198.     else
  199.         return compare(sl2,sl1);
  200.  
  201. }
  202.  
  203.  
  204.  
  205.  
  206. static priority_queue<seq_item,SWEEP_point> X_structure;
  207.  
  208. static sortseq<SWEEP_segment,pq_item> Y_structure;
  209.  
  210.  
  211. bool intersection(SWEEP_segment seg1,SWEEP_segment seg2, SWEEP_point& inter)
  212. {
  213.   if (seg1->slope == seg2->slope)
  214.     return false;
  215.   else
  216.   {
  217.     //x-coordinate  of the intersection
  218.     double Cross_x = (seg2->yshift - seg1->yshift) / (seg1->slope - seg2->slope);
  219.  
  220.     if (Cross_x <= x_sweep) return false;
  221.  
  222.     double s1 = seg1->startpoint->x;
  223.     double s2 = seg2->startpoint->x;
  224.     double e1 = seg1->endpoint->x;
  225.     double e2 = seg2->endpoint->x;
  226.  
  227.     if (s2>Cross_x || s1>Cross_x || Cross_x>e1 || Cross_x>e2) return false;
  228.  
  229.     //y-coordinate of the intersection
  230.     double Cross_y = (seg1->slope * Cross_x + seg1->yshift);
  231.     inter =  new SWEEP_POINT(Cross_x,Cross_y);
  232.  
  233.     return true;
  234.   }
  235. }
  236.  
  237. void message(string s, int line=1)
  238. { s += "                                                            ";
  239.   double d = 20/Wp->scale();
  240.   if (s.length() > 150) s = s.head(150);
  241.   Wp->draw_text(Wp->xmin()+d, Wp->ymax()-d*(0.5+line),s);
  242.  }
  243.  
  244.  
  245. void draw_segment(SWEEP_segment seg)
  246. { double x1 = get_x(get_startpoint(seg));
  247.   double y1 = get_y(get_startpoint(seg));
  248.   double x2 = get_x(get_endpoint(seg));
  249.   double y2 = get_y(get_endpoint(seg));
  250.  
  251.   double d = 10/Wp->scale();
  252.  
  253.   Wp->draw_text(x1-d,y1,string("%d",get_name(seg)));
  254.  
  255.   Wp->draw_segment(x1,y1,x2,y2,seg_color);
  256. }
  257.  
  258.  
  259.  
  260.  
  261. void draw_sweep_line(double xpos) 
  262. {
  263.   Wp->set_mode(xor_mode);
  264.   Wp->draw_segment(xpos,-1150,xpos,Wp->ymax()-5*20/Wp->scale());
  265.   Wp->set_mode(src_mode);
  266. }
  267.  
  268.  
  269. void move_sweep_line(double x, double xpos) 
  270. { 
  271.   if (x == xpos) return;
  272.  
  273.   double delta = 1/Wp->scale(); 
  274.   double y = Wp->ymax()-100*delta;
  275.  
  276.   Wp->set_mode(xor_mode);
  277.  
  278.   while (x < xpos)
  279.   { Wp->draw_segment(x+delta,-1150,x+delta,y);
  280.     Wp->draw_segment(x,-1150,x,y);
  281.     x += delta;
  282.    }
  283.   
  284.   Wp->draw_segment(x,-1150,x,y);
  285.   Wp->draw_segment(xpos,-1150,xpos,y);
  286.  
  287.   Wp->set_mode(src_mode);
  288. }
  289.  
  290.  
  291.  
  292. void draw_Ystructure()
  293. {
  294.   seq_item sit;
  295.   string s = "Y_structure: ";
  296.  
  297.   forall_items(sit,Y_structure) 
  298.     s+=string("%d ",get_name(Y_structure.key(sit)));
  299.  
  300.   message(s,3);
  301.  
  302. }
  303.  
  304. void draw_Xstructure()
  305. {
  306.   string s = "X_structure: ";
  307.  
  308.   priority_queue<seq_item,SWEEP_point> Q = X_structure;
  309.  
  310.   while (!Q.empty())
  311.   { pq_item it = Q.find_min(); 
  312.  
  313.     SWEEP_point p = X_structure.inf(it);
  314.     seq_item sit  = X_structure.key(it);
  315.  
  316.     Q.del_min();
  317.  
  318.      SWEEP_segment seg = get_seg(p);
  319.  
  320.      switch (get_kind(p)) {
  321.  
  322.      case Leftend:  s += string("L(%d) ",get_name(seg));
  323.                     break;
  324.  
  325.      case Rightend: s += string("R(%d) ",get_name(seg)) ;
  326.                     break;
  327.  
  328.      default:       s += string("X(%d) ",get_name(Y_structure.key(sit))); 
  329.                     break;
  330.  
  331.      }
  332.  
  333.   }
  334.  
  335.   message(s,2);
  336.  
  337. }
  338.  
  339. pq_item Xinsert(seq_item i, SWEEP_point p) 
  340. { 
  341.  
  342.  if (trace)
  343.  {
  344.   SWEEP_segment s ;
  345.   if (i!=nil) s = Y_structure.key(i);
  346.  
  347.   else s = get_seg(p);
  348.     
  349.      switch (get_kind(p)) {
  350.  
  351.      case Leftend:  message(string("Xinsert: L(%d) ",get_name(s)),4);
  352.                     break;
  353.  
  354.      case Rightend: message(string("Xinsert: R(%d) ",get_name(s)),4) ;
  355.                     break;
  356.  
  357.      default:       message(string("Xinsert: X(%d) ",get_name(s)),4); 
  358.                     break;
  359.       }
  360.  
  361.   Wp->set_mode(xor_mode);
  362.   Wp->draw_filled_node(get_x(p),get_y(p),green);
  363.   Wp->set_mode(src_mode);
  364.  }
  365.   return X_structure.insert(i,p);
  366. }
  367.  
  368. SWEEP_point Xdelete(pq_item i) 
  369. {
  370.  if (trace)
  371.  {SWEEP_point p = X_structure.inf(i);
  372.  
  373.   seq_item sit = X_structure.key(i);
  374.  
  375.   SWEEP_segment s ;
  376.  
  377.   if (sit!=nil) s = Y_structure.key(sit);
  378.   else s = get_seg(p);
  379.     
  380.      switch (get_kind(p)) {
  381.  
  382.      case Leftend:  message(string("Xdelete: L(%d) ",get_name(s)),4);
  383.                     break;
  384.  
  385.      case Rightend: message(string("Xdelete: R(%d) ",get_name(s)),4) ;
  386.                     break;
  387.  
  388.      default:       message(string("Xdelete: X(%d) ",get_name(s)),4); 
  389.                     break;
  390.       }
  391.  
  392.   Wp->set_mode(xor_mode);
  393.   Wp->draw_filled_node(get_x(p),get_y(p),green);
  394.   Wp->set_mode(src_mode);
  395.  }
  396.  
  397.   SWEEP_point p = X_structure.inf(i);
  398.  
  399.   X_structure.del_item(i);
  400.  
  401.   return p;
  402. }
  403.  
  404.  
  405.  
  406. /*
  407. node New_Node(GRAPH<point,int>& G,double x, double y )
  408. { return G.new_node(point(x,y)); }
  409.  
  410. void New_Edge(GRAPH<point,int>& G,node v, node w, SWEEP_segment l )
  411. { if (get_orient(l)==0)
  412.        G.new_edge(v,w,get_color(l));
  413.   else G.new_edge(w,v,get_color(l));
  414. }
  415. */
  416.  
  417.  
  418. void process_vertical_segment(/*GRAPH<point,int>& SUB, */ SWEEP_segment l)
  419. { 
  420.   SWEEP_point p = 
  421.               new SWEEP_POINT(get_x(get_startpoint(l)),get_y(get_startpoint(l)));
  422.   SWEEP_point q = 
  423.               new SWEEP_POINT(get_x(get_endpoint(l)),get_y(get_endpoint(l)));
  424.  
  425.   SWEEP_point r = new SWEEP_POINT(get_x(p)+1,get_y(p));
  426.   SWEEP_point s = new SWEEP_POINT(get_x(q)+1,get_y(q));
  427.  
  428.   SWEEP_segment bot = new SWEEP_SEGMENT(p,r,0,0);
  429.   SWEEP_segment top = new SWEEP_SEGMENT(q,s,0,0);
  430.  
  431.   seq_item bot_it = Y_structure.insert(bot,nil);
  432.   seq_item top_it = Y_structure.insert(top,nil);
  433.   seq_item sit;
  434.  
  435.   //node u,v,w;
  436.  
  437.   SWEEP_segment seg;
  438.   
  439.  
  440.   for(sit=Y_structure.succ(bot_it); sit != top_it; sit=Y_structure.succ(sit))
  441.   { seg = Y_structure.key(sit);
  442.  
  443.     double cross_y = (get_slope(seg) * get_x(p) + get_yshift(seg));
  444.  
  445.     Wp->draw_filled_node(get_x(p),cross_y,node_color);
  446.  
  447. /*
  448.     v = get_left_node(seg);
  449.     if (v==nil)
  450.     { w = New_Node(SUB,get_x(p),cross_y);
  451.       set_left_node(seg,w);
  452.      }
  453.     else
  454.     { double vx = SUB[v].xcoord();
  455.       if ( vx < get_x(p)-EPS2) 
  456.       { w = New_Node(SUB,get_x(p),cross_y);
  457.         New_Edge(SUB,v,w,seg);
  458.         set_left_node(seg,w);
  459.        }
  460.       else w = v;
  461.      }
  462.  
  463.     u = get_left_node(l);
  464.     if (u!=nil && u!=w) New_Edge(SUB,u,w,l);
  465.     set_left_node(l,w);
  466. */
  467.  
  468.    }
  469.     
  470.   delete l;
  471.   delete bot;
  472.   delete top;
  473.   Y_structure.del_item(bot_it);
  474.   Y_structure.del_item(top_it);
  475.  
  476.  }
  477.  
  478.  
  479. void plane_sweep(list<segment>& L1, list<segment>& L2 
  480.                  /*, GRAPH<point,int>& SUB */)
  481. {
  482.   SWEEP_point    p,inter;
  483.   SWEEP_segment  seg, l,lsit,lpred,lsucc,lpredpred;
  484.  
  485.   pq_item  pqit,pxmin;
  486.   seq_item sitmin,sit,sitpred,sitsucc,sitpredpred;
  487.  
  488.  
  489.   int count=1;
  490.  
  491.   Wp->clear();
  492.  
  493.   //initialization of the X-structure
  494.  
  495.   segment s;
  496.  
  497.   forall(s,L1) 
  498.    { SWEEP_point p = new SWEEP_POINT(s.start());
  499.      SWEEP_point q = new SWEEP_POINT(s.end());
  500.      seg = new SWEEP_SEGMENT(p,q,0,count++);
  501.      draw_segment(seg);
  502.      Xinsert(nil,get_startpoint(seg));
  503. /*
  504. Print(seg);
  505. Print(get_startpoint(seg));
  506. newline;
  507. */
  508.    }
  509.  
  510.   count = -1;
  511.  
  512.   forall(s,L2) 
  513.    { SWEEP_point p = new SWEEP_POINT(s.start());
  514.      SWEEP_point q = new SWEEP_POINT(s.end());
  515.      seg = new SWEEP_SEGMENT(p,q,1,count--);
  516.      draw_segment(seg);
  517.      Xinsert(nil,get_startpoint(seg));
  518. /*
  519. Print(seg);
  520. Print(get_startpoint(seg));
  521. newline;
  522. */
  523.    }
  524.  
  525.  
  526.   count = 0;
  527.  
  528.   x_sweep = Wp->xmin();
  529.   y_sweep = Wp->ymin();
  530.  
  531.   if (trace)
  532.   { draw_Xstructure();
  533.     draw_Ystructure();
  534.    }
  535.  
  536.   draw_sweep_line(x_sweep);
  537.  
  538.   while(!X_structure.empty())
  539.   {
  540.     if (trace)  
  541.        trace = (Wp->read_mouse() != 3);
  542.     else
  543.        trace = Wp->get_button();
  544.  
  545.  
  546.     pxmin = X_structure.find_min();
  547.     p = X_structure.inf(pxmin);
  548.  
  549.     move_sweep_line(x_sweep,get_x(p));
  550.  
  551.     sitmin = X_structure.key(pxmin);
  552.  
  553.     Xdelete(pxmin);
  554.  
  555.  
  556.  
  557.     if (get_kind(p) == Leftend)
  558.  
  559.     //left endpoint
  560.     { 
  561.  
  562.       l = get_seg(p); 
  563.  
  564.       x_sweep = get_x(p);
  565.       y_sweep = get_y(p);
  566.  
  567.       if (trace)
  568.       message(string("LEFT  point   x = %4f seg = %4d",
  569.               get_x(p),get_name(l)),1);
  570.  
  571.  
  572.       if (get_x(p) == get_x(get_endpoint(l)))
  573.         process_vertical_segment(/*SUB,*/ l);
  574.       else
  575.       {
  576.  
  577.       sit = Y_structure.lookup(l);
  578.  
  579.       if (sit!=nil)  error_handler(0,"plane sweep: sorry, overlapping segments");
  580.  
  581.       sit = Y_structure.insert(l,nil);
  582.  
  583.       Xinsert(sit,get_endpoint(l));
  584.  
  585.       sitpred = Y_structure.pred(sit);
  586.       sitsucc = Y_structure.succ(sit);
  587.  
  588.       if (sitpred != nil) 
  589.       { if ((pqit = Y_structure.inf(sitpred)) != nil)
  590.           delete Xdelete(pqit);
  591.  
  592.         lpred = Y_structure.key(sitpred);
  593.  
  594.         Y_structure.change_inf(sitpred,nil);
  595.  
  596.         if (intersection(lpred,l,inter))
  597.             Y_structure.change_inf(sitpred,Xinsert(sitpred,inter));
  598.       }
  599.  
  600.  
  601.       if (sitsucc != nil)
  602.       { lsucc = Y_structure.key(sitsucc);
  603.         if (intersection(lsucc,l,inter))
  604.            Y_structure.change_inf(sit,Xinsert(sit,inter));
  605.       }
  606.      } /* else if vertical */
  607.  
  608.     }
  609.     else if (get_kind(p) == Rightend)
  610.          //right endpoint
  611.          { 
  612.            x_sweep = get_x(p);
  613.            y_sweep = get_y(p);
  614.  
  615.            if (trace)
  616.            message(string("RIGHT point   x = %4f seg = %4d",
  617.                    get_x(p),get_name(get_seg(p))),1);
  618.  
  619.            sit = sitmin;
  620.  
  621.            sitpred = Y_structure.pred(sit);
  622.            sitsucc = Y_structure.succ(sit);
  623.  
  624.            SWEEP_segment SEG =Y_structure.key(sit);
  625.  
  626.            Y_structure.del_item(sit);
  627.  
  628.            delete SEG;
  629.  
  630.            if((sitpred != nil)&&(sitsucc != nil))
  631.            {
  632.              lpred = Y_structure.key(sitpred);
  633.              lsucc = Y_structure.key(sitsucc);
  634.              if (intersection(lsucc,lpred,inter))
  635.                 Y_structure.change_inf(sitpred,Xinsert(sitpred,inter));
  636.            }
  637.          }
  638.          else /*point of intersection*/
  639.          { 
  640.            //node w = New_Node(SUB,get_x(p),get_y(p));
  641.  
  642.            count++;
  643.  
  644.            /* Let L = list of all lines intersecting in p 
  645.  
  646.               we compute sit     = L.head();
  647.               and        sitpred = L.tail();
  648.  
  649.               by scanning the Y_structure in both directions 
  650.               starting at sitmin;
  651.  
  652.            */
  653.  
  654.            /* search for sitpred upwards from sitmin: */
  655.  
  656.            Y_structure.change_inf(sitmin,nil);
  657.  
  658.            sitpred = Y_structure.succ(sitmin);
  659.  
  660.  
  661.            while ((pqit=Y_structure.inf(sitpred)) != nil)
  662.            { SWEEP_point q = X_structure.inf(pqit);
  663.              if (compare(p,q) != 0) break; 
  664.              X_structure.del_item(pqit);
  665.              Y_structure.change_inf(sitpred,nil);
  666.              sitpred = Y_structure.succ(sitpred);
  667.             }
  668.  
  669.  
  670.            /* search for sit downwards from sitmin: */
  671.  
  672.            sit = sitmin;
  673.  
  674.            seq_item sit1;
  675.            
  676.            while ((sit1=Y_structure.pred(sit)) != nil)
  677.            { pqit = Y_structure.inf(sit1);
  678.              if (pqit == nil) break;
  679.              SWEEP_point q = X_structure.inf(pqit);
  680.              if (compare(p,q) != 0) break; 
  681.              X_structure.del_item(pqit);
  682.              Y_structure.change_inf(sit1,nil);
  683.              sit = sit1;
  684.             }
  685.  
  686.  
  687. /*
  688.            if (trace)
  689.            { string line;
  690.              line += string("sit = %d  ", get_name(Y_structure.key(sit)));
  691.              line += string("sitpred = %d",get_name(Y_structure.key(sitpred)));
  692.              message(line,5);
  693.             }
  694. */
  695.  
  696. /*
  697.  
  698.            // insert edges to p for all segments in sit, ..., sitpred into SUB
  699.            // and set left node to w 
  700.  
  701.            lsit = Y_structure.key(sitpred);
  702.  
  703.            node v = get_left_node(lsit);
  704.            if (v!=nil) New_Edge(SUB,v,w,lsit);
  705.            set_left_node(lsit,w);
  706.  
  707.            for(sit1=sit; sit1!=sitpred; sit1 = Y_structure.succ(sit1))
  708.            { lsit = Y_structure.key(sit1);
  709.  
  710.              v = get_left_node(lsit);
  711.              if (v!=nil) New_Edge(SUB,v,w,lsit);
  712.              set_left_node(lsit,w);
  713.             }
  714. */
  715.  
  716.            lsit = Y_structure.key(sit);
  717.            lpred=Y_structure.key(sitpred);
  718.            sitpredpred = Y_structure.pred(sit);
  719.            sitsucc=Y_structure.succ(sitpred);
  720.  
  721.            message(string("INTERSECTION  # = %4d  x = %5f  seg = %4d ",
  722.                         count, float(get_x(p)),get_name(lsit)),1);
  723.  
  724.            draw_sweep_line(get_x(p));
  725.            Wp->draw_filled_node(get_x(p),get_y(p),node_color);
  726.            draw_sweep_line(get_x(p));
  727.  
  728.  
  729.            if (sitpredpred != nil)
  730.             { 
  731.               lpredpred=Y_structure.key(sitpredpred);
  732.  
  733.               if ((pqit = Y_structure.inf(sitpredpred)) != nil)
  734.                delete Xdelete(pqit);
  735.      
  736.  
  737.               Y_structure.change_inf(sitpredpred,nil);
  738.  
  739.  
  740.               if (intersection(lpred,lpredpred,inter))
  741.                 Y_structure.change_inf(sitpredpred,
  742.                                        Xinsert(sitpredpred,inter));
  743.              }
  744.  
  745.  
  746.            if (sitsucc != nil)
  747.             {
  748.               lsucc=Y_structure.key(sitsucc);
  749.  
  750.               if ((pqit = Y_structure.inf(sitpred)) != nil)
  751.                 delete Xdelete(pqit);
  752.                  
  753.               Y_structure.change_inf(sitpred,nil);
  754.  
  755.               if (intersection(lsucc,lsit,inter))
  756.                   Y_structure.change_inf(sit,Xinsert(sit,inter));
  757.              }
  758.  
  759.  
  760. // reverse the subsequence sit, ... ,sitpred  in the Y_structure
  761.  
  762.            x_sweep = get_x(p);
  763.            y_sweep = get_y(p);
  764.  
  765.            Y_structure.reverse_items(sit,sitpred);
  766.  
  767.            delete p;
  768.  
  769.          } // intersection
  770.  
  771.    if (trace) 
  772.     { draw_Xstructure();
  773.       draw_Ystructure();
  774.      }
  775.  
  776.   }
  777.  
  778.   message("END OF SWEEP",1);
  779.  
  780.   if (intera) Wp->read_mouse();             //wait for mouse click
  781.  
  782.     draw_sweep_line(x_sweep);
  783.  
  784.     X_structure.clear();
  785.  
  786. } // plane_sweep
  787.  
  788.  
  789.  
  790. void interactive(window& W)
  791. {
  792.   intera= true;
  793.  
  794.   int grid_width = 0;
  795.   int line_width = 1;
  796.   int node_width = 4;
  797.   int N = 80;
  798.  
  799.   panel P("PLANE SWEEP DEMO");
  800.  
  801.   P.bool_item("TRACE",trace);
  802.   P.int_item("GRID",grid_width,0,40,10);
  803.   P.int_item("SEGMENTS", N);
  804.   P.int_item("line width",line_width,1,5);
  805.   P.int_item("node width",node_width,1,10);
  806.   P.button("MOUSE");
  807.   P.button("RANDOM");
  808.   P.button("QUIT");
  809.  
  810.   for(;;)
  811.   { int input = P.open(W);
  812.   
  813.     if (input == 2) break;
  814.   
  815.     W.init(-1200,1200,-1200, grid_width);
  816.     W.set_text_mode(opaque);
  817.     W.set_node_width(node_width);
  818.     W.set_line_width(line_width);
  819.   
  820.     list<segment> seglist1,seglist2;
  821.   
  822.     if (input==1)  // random 
  823.      { init_random();
  824.        double ymax = W.ymax()-4*20/W.scale()-100;
  825.        int xmin = int(W.xmin())+100;
  826.        int xmax = int(W.xmax())-100;
  827.        for(int i=0; i<N; i++)
  828.        { double x1 = random(xmin,-100);
  829.          double y1 = random(-1000,int(ymax));
  830.          double x2 = random(100,xmax);
  831.          double y2 = random(-1000,int(ymax));
  832.          segment s(x1,y1,x2,y2);
  833.          W << s;
  834.          seglist1.append(s);
  835.         }
  836.       }
  837.     else // input == 0 (mouse)
  838.       { segment s;
  839.         while (W >> s)
  840.         { W << s;
  841.           seglist1.append(s);
  842.          }
  843.        }
  844.   
  845.   
  846.     plane_sweep(seglist1,seglist2);
  847.   
  848.   //GRAPH<point,int> SUB;
  849.   //plane_sweep(seglist1,seglist2,SUB);
  850.   
  851.  } // for(;;)
  852.  
  853. }
  854.  
  855.  
  856.  
  857. void demo(window& W, int N)
  858. {
  859.   trace = false;
  860.  
  861.   W.init(-1200,1200,-1200);
  862.  
  863.   for(;;)
  864.   {
  865.  
  866.   W.clear();
  867.  
  868.  
  869.   W.set_text_mode(opaque);
  870.   W.set_node_width(3);
  871.  
  872.  
  873.   list<segment> seglist1,seglist2;
  874.  
  875.      init_random();
  876.  
  877.      double ymax = W.ymax()-4*20/W.scale()-100;
  878.  
  879.      for(int i=0; i<N; i++)
  880.      { double x1 = random(-1100,-100);
  881.        double y1 = random(-1000,int(ymax));
  882.        double x2 = random(100,1100);
  883.        double y2 = random(-1000,int(ymax));
  884.        segment s(x1,y1,x2,y2);
  885.        W << s;
  886.        seglist1.append(s);
  887.       }
  888.  
  889.   plane_sweep(seglist1,seglist2);
  890.  
  891. /*
  892.   GRAPH<point,int> SUB;
  893.   edge e;
  894.  
  895.   plane_sweep(seglist1,seglist2,SUB);
  896.  
  897.   W.clear();
  898.   forall_edges(e,SUB) W <<  segment(SUB[source(e)],SUB[target(e)]);
  899. */
  900.  
  901.   wait(2);
  902.  
  903.   }
  904.  
  905. }
  906.  
  907.  
  908. /*
  909. #include <LEDA/stream.h>
  910. */
  911.  
  912.  
  913. main(int argc, char** argv)
  914. {
  915.   int N = 0;
  916.  
  917.   if (argc == 1)
  918.   { panel P0("PLANE SWEEP DEMO");
  919.     P0.text_item("This program computes the intersections in a set of");
  920.     P0.text_item("straight line segments using a plane sweep algorithm.");
  921.     P0.text_item("You can define the set of line segments interactively");
  922.     P0.text_item("using the left mouse button (input is terminated with");
  923.     P0.text_item("the right button) or create a random set of segments.");
  924.     P0.text_item("In TRACE mode the current contents of the event queue");
  925.     P0.text_item("(X-structure) and of the sweep line (Y-structure) are");
  926.     P0.text_item("displayed and the sweep line stops at each event point.");
  927.     P0.button("continue");
  928.     P0.open();
  929.    }
  930.   else
  931.     N = atoi(argv[1]);
  932.  
  933.   window W;
  934.  
  935.   Wp = &W;
  936.  
  937.   if (N==0) 
  938.       interactive(W);
  939.   else
  940.      demo(W,N);
  941.  
  942.  
  943.   return 0;
  944. }
  945.